package kele.lc;

import java.util.Arrays;

/**
 * @ClassName : greedyAlgorithms
 * @Author : kele
 * @Date: 2024/8/5 22:19
 * @Description : 贪心算法练习
 */
public class greedyAlgorithms {

    /**
     * n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
     * 你需要按照以下要求，给这些孩子分发糖果：
     * 每个孩子至少分配到 1 个糖果。
     * 相邻两个孩子评分更高的孩子会获得更多的糖果。
     * 请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目
     *
     * @param ratings
     */
    @Deprecated
    public static void candy2(int[] ratings) {

        int candy_sum = 1;
        int bef_candy = 1;
        int min = Integer.MAX_VALUE;
        int now_candy = 1;


        for (int i = 1; i < ratings.length; i++) {

            if (ratings[i] > ratings[i - 1]) {
                now_candy = bef_candy + 1;
            } else if (ratings[i] < ratings[i - 1]) {
                now_candy = bef_candy - 1;
            } else {
                if (i + 1 < ratings.length) {
                    if (ratings[i] > ratings[i - 1]) {
                        now_candy = bef_candy + 1;
                    } else {
                        now_candy = bef_candy - 1;
                    }
                }

            }

            candy_sum += now_candy;
            bef_candy = now_candy;
            System.out.print(now_candy + "\t");

            min = Math.min(min, now_candy);
        }
        System.out.println();

        if (min < 1) {
            candy_sum += (-min + 1) * ratings.length;
        }

        System.out.println(candy_sum);

    }

    /**
     * 题目是上一轮的
     * 贪心算法：
     * 思路： 两次遍历
     * ① 从左往右遍历，如果右边的大于左边的数字，则右边的糖果等于左边的糖果+1
     * ② 从右往左遍历，如果左边的大于右边的，则左边 = Max（本身或者右边的+1）
     *
     * @param ratings
     */
    public static void candy(int[] ratings) {

        int[] candy_num = new int[ratings.length];
        int candy_sum = 0;
        Arrays.fill(candy_num, 1);

        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candy_num[i] = candy_num[i - 1] + 1;
            }
        }

        for (int i = ratings.length - 2; i >= 0; i--) {

            if (ratings[i] > ratings[i + 1]) {
                candy_num[i] = Math.max(candy_num[i], candy_num[i + 1] + 1);
            }
            candy_sum += candy_num[i];
        }
        candy_sum += candy_num[ratings.length - 1];

        for (int i : candy_num) {
            System.out.print(i + "\t");
        }
        System.out.println();

        System.out.println(candy_sum);
    }


    /**
     * 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
     * 对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；
     * 并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，
     * 这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
     *
     * @param g:胃口值
     * @param s：饼干尺寸
     */
    public static void findContentChildren(int[] g, int[] s) {

        Arrays.sort(g);
        Arrays.sort(s);

        for (int i : s) {
            System.out.print(i + "\t");
        }
        System.out.println();

        if (g.length == 0 || s.length == 0) {
            System.out.println(0);
            return;
        }

        int j = 0;
        int num = 0;
        for (int i = 0; i < g.length; i++) {

            while (j < s.length) {
                if (g[i] <= s[j]) {
                    j++;
                    num++;
                    break;
                }
                j++;
            }
        }
        System.out.println(num);
    }

    /**
     * 假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种在相邻的地块上，它们会争夺水源，两者都会死去。
     * 给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。
     * 另有一个数 n，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true，不能则返回 false。
     *
     * 思路：
     *  查找连续相邻的0有多少个，(num-1)/2 就是连续的0能插入的花
     *  注意： 如果相邻的0在开头或者结尾，则需要考虑前后问题，可以在最开始和最末尾增加一个0
     * @param flowerbed
     * @param n
     */
    public static void canPlaceFlowers(int[] flowerbed, int n) {

        int num = 0;
        int sum = 0;

        boolean flag = false;
        for (int i = -1; i <= flowerbed.length; i++) {

            if (i == -1 || i == flowerbed.length || flowerbed[i] == 0){
                if (!flag) {
                    num = 1;
                    flag = true;
                } else {
                    num++;
                }
            } else {
                flag = false;
                sum += ((num-1) / 2);
            }

            System.out.print(flag + "\t");
        }
        sum += ((num-1) / 2);
        System.out.println();
        System.out.println(sum);
        if(sum >= n){
            System.out.println(true);
        }else{
            System.out.println(false);
        }


    }

    public static void main(String[] args) {
//        candy(new int[]{1, 2, 87, 87, 87, 2, 1});
//        findContentChildren(new int[]{10, 9, 8, 7}, new int[]{5, 6, 7, 8});
//        findContentChildren(new int[]{10, 9, 8, 7}, new int[]{3});
        canPlaceFlowers(new int[]{1,0,0,0,1,0,0}, 1);
    }

}
